| class FSET{T} < $COPY |
|---|
| **** | Faster (hopefully!) version of FSET that switches from an FLIST to an FSET at the first amortized doubling. Hash array based sets of objects of type T requiring writebacks.
_ If T is a subtype of $NIL, then `nil' may not be an element, otherwise the type's default value may not be a element. _ If T is a subtype of $IS_EQ, then `is_eq' will be used for element equality (eg. string equality for STR), otherwise object equality is used. _ If T is a subtype of $HASH, then `hash' will be used for the hash value, otherwise the element `id' will be used. _ May be inherited with `elt_eq', `elt_nil', and `elt_hash' redefined to get a different behavior. The tables grow by amortized doubling and so require writeback when inserting and deleting elements. We keep down the load factor to cut down on collision snowballing. The simple collision resolution allows us to support deletions, but makes the behavior with poor hash functions quadratic. Puts a sentinel at the end of the table to avoid one check while searching. See the notes associated with an ORIG_FSET. For laziness reasons, the old FSET has been renamed to ORIG_FSET __(slow_fset) |
| $COPY | AREF{_} |
| attr use_map: BOOL; |
|---|
| **** | True if using the space as a map |
| aclear |
|---|
| **** | Set each element of self to nil. Built-in. |
| acopy(src:SAME) |
|---|
| **** | Copy as many elements from `src' to self as will fit. Built-in. |
| acopy(beg:INT, src:SAME) |
|---|
| **** | Copy as many elements from `src' to self as will fit when starting at index `beg' of self. |
| acopy(beg,num:INT, src:SAME) |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self. |
| acopy(beg,num,srcbeg:INT, src:SAME) |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in. |
| aget(ind:INT):T |
|---|
| **** | The element of self with index `ind'. Built-in. |
| aset(ind:INT, val:T) |
|---|
| **** | Set the element of self with index `ind' to `val'. Built-in. |
| asize:INT |
|---|
| **** | The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in. |
| changed_map(old,n: SAME): BOOL |
|---|
| **** | if ~old.use_map and n.use_map then #OUT+"Transitioning to use map. Size="+old.size+"\n";
_____end; |
| clear:SAME |
|---|
| **** | Clear out self, return the space if it has 17 or less entries otherwise return void. Self may be void. |
| copy:SAME |
|---|
| **** | A copy of self. |
| create(arr: ARRAY{T}): SAME |
|---|
| create(n:INT):SAME |
|---|
| **** | Make a table capable of dealing with `n' elements without expansion. You can simply insert into a void table to create one as well. Self may be void (and often is). |
| create:SAME |
|---|
| create_from(a: $CONTAINER{T}): SAME |
|---|
| delete(e:T):SAME |
|---|
| **** | A possibly new table which deletes the element `e' if it is contained in self. Doesn't modify the table if arg is not contained. Usage: `tbl:=tbl.delete(e)'. Self may be void. |
| delete_list(e: T): SAME |
|---|
| delete_map(e: T): SAME |
|---|
| difference(s:SAME):SAME |
|---|
| **** | A new set which is the difference between self and `s'. Self may be void. |
| elt_eq(e1,e2:ETP):BOOL |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| equals(s:SAME):BOOL |
|---|
| **** | True if `s' has the same elements as self. Self may be void. |
| first_elt:T |
|---|
| **** | The first element in the table, if any, otherwise elt_nil. |
| get(e:T):T |
|---|
| **** | If `e' is `elt_eq' to a table entry, return that entry, otherwise return `elt_nil'. Useful when different objects are treated as equal (eg. a table of strings used to get a unique representative for each class of equal strings). Self may be void. |
| get_list(e: T): T |
|---|
| get_map(e: T): T |
|---|
| has(e: T): BOOL |
|---|
| insert(e:T):SAME |
|---|
| **** | A possibly new table which includes `e'. If an entry is `elt_eq' to `e' then overwrite it with `e'. Usage: `tbl:=tbl.insert(e)'. Creates a new table if void(self). |
| insert_hash(r: SAME,e:T): SAME |
|---|
| insert_list(r: SAME,e:T): SAME |
|---|
| **** | If this is called, there should be at least enough space for one more insert Check for existing element first |
| intersect(s:SAME):SAME |
|---|
| **** | A new set which is the intersection of self and s. Self may be void. |
| intersects(s:SAME):BOOL |
|---|
| **** | True if self and `s' have elements in common. Self may be void. |
| is_disjoint_from(s:SAME):BOOL |
|---|
| **** | True if self and `s' have no elements in common. Self may be void. |
| is_elt_nil(e:ETP):BOOL |
|---|
| is_empty:BOOL |
|---|
| **** | True if the set is empty. Self may be void. |
| is_subset(s:SAME):BOOL |
|---|
| **** | True if all elements of self are contained in `s'. Self may be void. |
| size:INT |
|---|
| **** | Number of entries in the table. Self may be void. |
| str: STR |
|---|
| sym_difference(s:SAME):SAME |
|---|
| **** | A new set which is the symmetric difference between self and `s'. Self may be void. |
| test(e:T):BOOL |
|---|
| **** | True if `e' is `elt_eq' to an element contained in self. Self may be void. |
| test_list(e: T): BOOL |
|---|
| test_map(e: T): BOOL |
|---|
| to_difference(s:SAME):SAME |
|---|
| **** | The difference of self and `s', modifies self. Self may be void. |
| to_intersect(s:SAME):SAME |
|---|
| **** | The intersection of self and `s', modifies self. Self may be void. Can't think of a way to do this in place. |
| to_sym_difference(s:SAME):SAME |
|---|
| **** | The symmetric difference of self and `s', modifies self. Self may be void. |
| to_union(s:SAME):SAME |
|---|
| **** | The union of self and `s', modifies self. Self may be void. |
| union(s:SAME):SAME |
|---|
| **** | A new set which is the union of self and `s'. Self may be void. |
| aelt!(once beg:INT):T |
|---|
| **** | Yield each element of self starting at `beg'. Built-in. |
| aelt!(once beg,once num:INT):T |
|---|
| **** | Yield `num' successive elements of self starting at index `beg'. Built-in. |
| aelt!(once beg,once num,once step:INT):T |
|---|
| **** | Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in. |
| aelt!:T |
|---|
| **** | Yield each element of self in order. Built-in. |
| aind!:INT |
|---|
| **** | Yield the indices of self in order. |
| aset!(val:T) |
|---|
| **** | Set successive elements of self to the values `val'. Built-in. |
| aset!(once beg:INT,val:T) |
|---|
| **** | Set successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num:INT,val:T) |
|---|
| **** | Set `num' successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num,once step:INT, val:T) |
|---|
| **** | Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero. |
| elt!:T |
|---|
| **** | Yield the elements in self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| allocate(n:INT):SAME |
|---|
| **** | Allocate `n' locations (must be power of 2 plus 1) and initialize to `elt_nil'. |
| const default_initial_size: INT := 5; |
|---|
| **** | shared upward_transition_size: INT; shared downward_transition_size: INT; |
| double_size:SAME |
|---|
| **** | A new table of twice the size of self with self's entries copied over. |
| grow_if_necc: SAME |
|---|
| **** | Return a new map if it is necessary to grow it, otherwise return self |
| halve_size:SAME |
|---|
| **** | A new table of half the size of self with self's entries copied over. For now, don't transition downward |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| is_legal_aelts_arg( beg, num, step:INT) :BOOL |
|---|
| **** | True if the arguments are legal values for `aelts'. |
| const load_ratio:INT:=4; |
|---|
| **** | Allow to be at most 1/load_ratio full |
| not_too_many(start, finish:INT):BOOL |
|---|
| **** | A function called in an assert to check that really bad hashing isn't happening, which would probably be a performance bug. Since it is in an assert, this isn't called unless checking is on. |
| set_initial_structure |
|---|
| should_shrink:BOOL |
|---|
| switch_structure(is_old_map: BOOL, is_new_map: BOOL) is |
|---|
| **** | Isolate this as a function to make changes easier |
| const switch_structures: BOOL := true; |
|---|
| **** | Indicates whether the data structure should switch after the first allocate |
| attr use_map: BOOL; |
|---|
| **** | True if using the space as a map |
| const use_map_initially: BOOL := false; |
|---|
| **** | Indicates whether the data structure should start out with a map |